import java.util.Arrays;

public class FibonacciSequence {
    public static void main(String[] args) {
        System.out.println(f(3));
        System.out.println(feibo(0));
    }


    //斐波那契数列,时间复杂度 1.618的n次方
    public static int f(int n){
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        int x = f(n-1);
        int y = f(n-2);
        return x+y;
    }

    //改良版，时间复杂度O(n)
    public static int feibo(int n){
        int[] m = new int[n+1];
        Arrays.fill(m,-1);//把数组初始值都为-1
        //数列前两项已知
        m[0] = 0;
        m[1] = 1;
        return f1(n,m);
    }

    public static int f1(int n,int[] m){
        if (m[n] != -1){
            return m[n];
        }
        int x = f1(n-1,m);
        int y = f1(n-2,m);
        m[n] = x+y;
        return m[n];
    }
}
